import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;

public class Solution {
    public int StrToInt(String str) {
        if(str.trim().length()==0){
            return 0;
        }
        char [] arr=str.toCharArray();
        int flag=1;
        int i=0;
        if(arr[0]=='+'){
            i++;
        }
        if(arr[0]=='-'){
            i++;
            flag=-flag;
        }
        int answer=0;
        for(;i<arr.length;i++){
            int tmp=arr[i]-'0';
            if(tmp<0||tmp>9){
               return 0;
            }else{
            answer=answer+tmp;
            answer=answer*10;
            }    
        }
        return flag==1?answer:answer*flag;
    }
        public void rotate(int[][] matrix) {
            int right=matrix[0].length;
            int down=matrix.length;
            int[] [] arr=new int[right][down];
            int left=right-1;
            for(int i=0;i<down;i++){
                for(int j=0;j<right;j++){
                    arr[j][left]=matrix[i][j];
                }
                left--;
            }
            for(int i=0;i<right;i++){
                for(int j=0;j<down;j++){
                    matrix[i][j]=arr[i][j];
                }
            }
            return ;
        }
    public void rotate1(int[][] matrix) {
        if(matrix.length==0){
            return ;
        }
        //水平方向翻转
        int right=matrix[0].length-1;
        int down =matrix.length-1;
        int left=0;int up=0;
        while(up<=down){
            while(left<=right){
                int tmp=matrix[up][left];
                matrix[up][left]=matrix[down][left];
                matrix[down][left]=tmp;
                left++;
            }
            up++;
            down--;
        }
        right=matrix[0].length-1;
        down =matrix.length-1;
        left=0;up=0;
        //对角线翻转
        while(up<=down){
            while(left<=right){
                if(left!=up){
                    int tmp=matrix[up][left];
                    matrix[up][left]=matrix[left][up];
                    matrix[left][up]=tmp;
                }
                left++;
            }
            up++;
        }
        return;
    }
    public HashSet<String> set=new HashSet<>();
    public int [] count;
    //0 表示还未处理
    //1 表示可以
    // -1 表示不可以
    public boolean wordBreak(String s, List<String> wordDict) {
        if(s.length()==0||wordDict.size()==0){
            return false;
        }
        count=new int[s.length()];
        for(String item:wordDict){
            set.add(item);
        }
        Arrays.fill(count,0);
        return wordBreakChild(s,0);
    }
    public boolean wordBreakChild(String s,int index){
        if(index==s.length()){
            return true;
        }
        if(count[index]!=0){//已经处理过
            return count[index]==1;
        }
        for(int i=index;i<s.length();i++){
            String sub=s.substring(index,i+1);
            if(!set.contains(sub)){
                continue;
            }
            boolean flag=wordBreakChild(s,i+1);
            if(flag==true){
                count[index]=1;
                return true;
            }
        }
        count[index]=-1;
        return false;
    }
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
}
